
\section{Allocating 2 Facilities to 3 Locations: The Proof of Theorem~\ref{thm:3locations}}
\label{s:3locations}

The proof of Theorem~\ref{thm:3locations} is based on the following extension of Theorem~\ref{thm:3agents} to 3-location instances. In fact, we can restate the whole proof of Theorem~\ref{thm:3agents} with 3 coalitions of agents instead of 3 agents. Then, using that any strategyproof mechanism is also partial group strategyproof \cite[Lemma~2.1]{LSWZ10}, we obtain the following:

\begin{corollary}\label{cor:3agents}
Let $F$ be any nice mechanism applied to 3-location instances with $n \geq 3$ agents. Then, there exist at most two permutations $\pi_1$, $\pi_2$ of the agent coalitions with $\pi_1(2) = \pi_2(2)$ such that for all instances $\vec{x}$ where the coalitions are arranged on the line according to $\pi_1$ or $\pi_2$, $F(\vec{x})$ places a facility at the location of the middle coalition. For any other permutation $\pi$ and instance $\vec{x}$, where the agent coalitions are arranged on the line according to $\pi$, $F(\vec{x}) = ( \min \vec{x}, \max \vec{x} )$.
\end{corollary}

A central notion in the proof of Theorem~\ref{thm:3locations} is that of a \emph{dictator coalition}. A (non-empty) coalition $C \subset N$, $|C| \leq |N|-2$, is called a dictator for 3-location instances, if for all partitions $N_1, N_2$ of $N \setminus C$ and all instances $\vec{x} = (x_1\sep N_1, x\sep C, x_2\sep N_2) \in \Ithr(N)$, $x \in F(\vec{x})$.
%
The first main step of the proof is to show that if there exists a 3-location instance where the middle coalition has at most $n-3$ agents and is allocated a facility, then any superset of the middle coalition is a dictator for 3-location instances.

\begin{lemma}\label{l:any-partition}
Let $N$ be a set of $n \geq 4$ agents. If there exists a 3-location instance $\vec{x} = (x_1\sep N_1, x_2\sep N_2, x_3\sep N_3)$ with $x_1 < x_2 < x_3$ and $|N_2| \leq n-3$, such that $x_2 \in F(\vec{x})$, then any coalition $N'_2 \supseteq N_2$ is a dictator for 3-location instances.
\end{lemma}

\begin{proofsketch}
We consider any 3-location instance $\vec{y} = (y_1\sep N'_1, y_2\sep N'_2, y_3\sep N'_3)$ with $N'_2 \supseteq N_2$, and show that $y_2 \in F(\vec{y})$.
%
For the proofsketch, we assume that $y_1 < y_3$, that $|N_1| \geq 2$, and that $N_1 \cut N'_1 \neq \emptyset$ (these assumptions can be easily removed). We start from instance $(y_1\sep N_1, y_2\sep N_2, y_3\sep N_3)$, where $F$ allocates a facility to $N_2$, by Corollary~\ref{cor:3agents}, due to the existence of instance $\vec{x}$. The key step is to show that we can move agents between the coalitions, and thus obtain the desired partition $N'_1, N'_2, N'_3$, while keeping a facility of $F$ allocated to the middle coalition. Then, the lemma follows from Corollary~\ref{cor:3agents}.

To this end, we first consider the instance $\vec{y}' = (y_1\sep N_1, y_1+\eps\sep N_2, y_3\sep N_3)$, where $\eps > 0$ is chosen small enough that due to $F$'s bounded approximation ratio, the rightmost facility of $F(\vec{y}')$ is placed at the right of $y_1+\eps$. By Corollary~\ref{cor:3agents}, $y_1+\eps \in F(\vec{y}')$.
%
We observe that as long as there are at least two agents at $y_1$, we can move either some agent $j \in N_1 \cut N'_2$ from $y_1$ to $y_1+\eps$ or some agent $j \in N_1 \cut N'_3$ from $y_1$ to $y_3$, while keeping a facility of $F$ to $y_1+\eps$.
%
In particular, if the middle coalition is not allocated a facility after $j$'s move to $y_3$, Corollary~\ref{cor:3agents} implies that the two facilities are placed at $y_1$ and $y_3$. Therefore, agent $j$ in instance $\vec{y}'$ could manipulate $F$ by reporting $y_3$ instead of $y_1$.
%
By repeatedly applying this argument, we obtain an instance $\vec{z} = (y_1\sep Z_1, y_1+\eps\sep Z_2, y_3\sep Z_3)$ such that $Z_1 = N_1 \cut N'_1 \neq \emptyset$, $Z_2 = N_2 \union (N_1 \cut N'_2)$, $Z_3 = N_3 \union (N_1 \cut N'_3)$, and $y_1+\eps \in F(\vec{z})$.

Next, we consider the instance $\vec{z}' = (y_1\sep Z_1, y_3-\eps'\sep Z_2, y_3\sep Z_3)$, where $\eps' > 0$ is chosen small enough that the leftmost facility of $F(\vec{z}')$ is located on the left of $y_3-\eps'$. By Corollary~\ref{cor:3agents}, $y_3-\eps' \in F(\vec{z}')$.
%
As before, we move all agents in $Z_3 \cut N'_2$ from the right to the middle coalition and all agents in $Z_3 \cut N'_1$ from the right to the left coalition, and obtain the instance $\vec{y}'' = (y_1\sep N'_1, y_3-\eps\sep N'_2, y_3\sep N'_3)$, where $y_3-\eps \in F(\vec{y}'')$.
%
Since $F$ allocates a facility to the middle coalition $N'_2$ of $\vec{y}''$, by Corollary~\ref{cor:3agents}, $F$ allocates a facility to $N'_2$ for all instances $\vec{y} = (y_1\sep N'_1, y_2\sep N'_2, y_3\sep N'_3)$. The details are deferred to the Appendix, Section~\ref{app:s:any-partition}.
\qed\end{proofsketch}

For technical reasons, we distinguish between instances where the largest coalition has size at most $n-3$, and instances where the largest coalition has size $n-2$ and the other two coalitions are singletons. Given a set $N$ of agents, we let $\IthrS(N)$ denote the former class and $\IthrL(N)$ denote the latter class of 3-location instances. %We note that for all sets $N$ of $n \geq 5$ agents, $\IthrS(N)$ and $\IthrL(N)$ form a partition of $\Ithr(N)$.
The following lemma establishes Theorem~\ref{thm:3locations} for instances in $\IthrS(N)$.


%The following lemmas establish Theorem~\ref{thm:3locations} for instances in $\IthrS(N)$ and instances in $\IthrL(N)$ separately. The proof of Lemma~\ref{l:unique-dictator-large} is similar to the proof of Lemma~\ref{l:unique-dictator-small}, and can be found in the Appendix, Section~\ref{app:s:unique-dictator-large}.


\begin{lemma}\label{l:unique-dictator-small}
Let $N$ be a set of $n \geq 5$ agents. If there exists an instance $\vec{x} = (x_1\sep N_1, x_2\sep N_2, x_3\sep N_3) \in \IthrS(N)$ with $x_1 < x_2 < x_3$, such that $x_2 \in F(\vec{x})$, then there exists a unique agent $j \in N_2$ such that for all instances $\vec{y} \in \IthrS(N)$, $y_j \in F(\vec{y})$.
\end{lemma}

\begin{proofsketch}
Let $\vec{x} = (x_1\sep N_1, x_2\sep N_2, x_3\sep N_3) \in \IthrS(N)$ with $x_1 < x_2 < x_3$, such that $x_2 \in F(\vec{x})$. Then, by Lemma~\ref{l:any-partition}, $N_2$ is a dictator for 3-location instances. For sake of contradiction, we assume that there is a minimal (sub)coalition $N'_2 \subseteq N_2$, $|N'_2| \geq 2$, that violates the lemma. Namely, $N'_2$ is a dictator for 3-location instances, while for every agent $j \in N'_2$, $N'_2 \setminus \{ j \}$ is not a dictator.
%
In the Appendix, Section~\ref{app:s:unique-dictator-small}, we show that for any agent $j \in N'_2$ and any agent $i \in N \setminus N'_2$, $\{ j, i \}$ is a dictator for 3-location instances.

Therefore, if we let $j_1, j_2$ be any two agents in the minimal dictator coalition $N'_2$, for any pair of agents $i_1, i_2 \in N \setminus N'_2$, the coalitions $\{ j_1, i_1 \}$ and $\{ j_2, i_2 \}$ are both dictators for 3-location instances.
%
But the existence of two disjoint dictator coalitions contradicts the hypothesis that $F$ has a bounded approximation ratio.
%
Let $\vec{z} = (0\sep  N \setminus \{j_1, i_1, j_2, i_2\}, 1\sep \{ j_1, i_1\}, 1+\eps\sep \{j_2, i_2\})$, where $\eps > 0$ is chosen sufficiently small. Since both $\{ j_1, i_1\}$ and $\{ j_2, i_2 \}$ are dictators, % for 3-location instances,
$F(\vec{z}) = (1, 1+\eps)$, which for a sufficiently small $\eps$, contradicts that $F$ has a bounded approximation ratio.

Therefore, there exists an agent $j \in N_2$ such that for all instances $\vec{y} \in \IthrS(N)$, $y_j \in F(\vec{y})$. The uniqueness of such an agent $j$ follows from a similar argument as above, due to $F$'s bounded approximation ratio.
\qed\end{proofsketch}


To conclude the proof of Theorem~\ref{thm:3locations}, we next show that $F$ behaves in the same way for all instances in $\Ithr(N)$. The proof of the following lemma is similar to the proof of Lemma~\ref{l:unique-dictator-small}, and can be found in the Appendix, Section~\ref{app:s:unique-dictator-large}.


\begin{lemma}\label{l:unique-dictator-large}
Let $N$ be a set of $n \geq 5$ agents. If there exists an instance $\vec{x} = (x_1\sep N_1, x_2\sep N_2, x_3\sep N_3) \in \IthrS(N)$ with $x_1 < x_2 < x_3$, such that $x_2 \in F(\vec{x})$, then there exists a unique agent $j \in N_2$ such that for all instances $\vec{y} \in \Ithr(N)$, $y_j \in F(\vec{y})$. Otherwise, for all instances $\vec{y} \in \Ithr(N)$, $F(\vec{y}) = (\min \vec{y}, \max \vec{y})$.
\end{lemma}




%If a coalition $C$ is a dictator for 3-location instances and not too large, we should expect that there is (at least one) agent $j \in C$ whose removal from $C$ results in a non-dictator coalition $C \setminus \{ j \}$. Otherwise, we could iteratively remove agents from $C$ in a different order, and obtain (at least) two disjoint dictator coalitions, which contradicts the hypothesis that $F$ has a bounded approximation ratio (see also the proof of Lemma~\ref{l:unique-dictator-small}). The following technical lemma states that such an agent $j$ is very close to being a dictator by herself, in the sense that by joining any other agent $i \in N \setminus C$, she builds a new dictator coalition $\{ j, i \}$. For technical reasons, the argument below establishes this property only for 3-location instances with at least $5$ agents.





\section{Strategyproof Allocation of 2 Facilities: The Proof of Theorem~\ref{thm:2fac-gen}}
\label{s:2fac-gen}

In this section, we extend Theorem~\ref{thm:3locations} to general instances with $n \geq 5$ agents, and conclude the proof of Theorem~\ref{thm:2fac-gen}. %In particular, we show that any nice mechanism applied to instances with $n \geq 5$ agents, either admits a dictator, or it always allocates the facilities to the two extreme locations of the instance.
The proof considers two different cases, depending on how the mechanism $F$ behaves for 3-location instances, and uses induction on the number of different locations.

We first consider the case where $F$ admits a dictator $j$ for 3-location instances, and show that agent $j$ is a dictator for all instances $\vec{x} \in \I(N)$.
%
For sake of contraction, we assume that there is an instance $\vec{x} = (x_1, \ldots, x_n) \in \I(N)$ for which $x_j \not\in F(\vec{x})$. Without loss of generality, we let $k \neq j$ be the rightmost agent of $\vec{x}$ (if $j$ is the rightmost agent, the argument is symmetric). Since $x_j \not\in F(\vec{x})$, there is a $x_j$-hole $(l, r)$ in the imageset $I_j(\vec{x}_{-j})$.
%
For a small $\eps \in (0, (r-l)/2)$, we consider the instance $\vec{x}_1 = (\vec{x}_{-j}, l+\eps)$, where $j$ moves from $x_j$ to $l+\eps$. By strategyproofness, and since $l+\eps$ is in the left half of the hole $(l, r)$, $l \in F(\vec{x}_1)$.
%
Then, we iteratively move all agents $i \in N \setminus \{j, k\}$ from $x_i$ to $l$. By strategyproofness, if $F$ has a facility at $l$ before an agent $i$  moves from $x_i$ to $l$, $F$ keeps its facility at $l$ after $i$'s move. Otherwise, agent $i$ with location $l$ could manipulate $F$ by reporting $x_i$.
%
Thus, we obtain a 3-location instance $\vec{x}' = (l\sep N \setminus \{j, k\}, l+\eps\sep \{j\}, x_k\sep \{k\})$ with $l < l+\eps < x_k$, such that $l \in F(\vec{x}')$. Moreover, since $j$ is a dictator for 3-location instances, $l+\eps \in F(\vec{x}')$, and thus $F(\vec{x}') = (l, l+\eps)$. For $\eps$ sufficiently smaller than $x_k - l$, this contradicts that $F$ has a bounded approximation ratio.


If $F$ does not admit a dictator for 3-location instances, by Theorem~\ref{thm:3locations}, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$ for all instances $\vec{x} \in \Ithr(N)$. Next, we show that in this case, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$ for all instances $\vec{x} \in \I(N)$.
%
For sake of contradiction, we assume that there is an instance $\vec{x} = (x_1, \ldots, x_n) \in \I(N)$, for which $F(\vec{x}) \neq (\min\vec{x}, \max\vec{x})$. We let $j$ be the leftmost and $k$ be the rightmost agent of $\vec{x}$. Since $F(\vec{x}) \neq (x_j, x_k)$, there is a location $a \in F(\vec{x})$ with $a \neq x_j$ and $a \neq x_k$.

If $x_j < a < x_k$, we iteratively move all agents $i \in N \setminus \{j, k\}$ from $x_i$ to $a$. As before, since $F$ is strategyproof, it keeps allocating a facility to $a$ after each agent $i$ moves to $a$. Thus, we obtain a 3-location instance $\vec{x}' = (x_j\sep \{j\}, a\sep N \setminus \{j, k\}, x_k\sep \{k\})$ for which $F$ does not place the facilities at the two extremes, a contradiction. %Therefore, for all instances $\vec{x} \in \I(N)$, $F(\vec{x})$ does not allocate a facility inside the two extremes.

We proceed to consider the case where $a < x_j$, %i.e., where $a$ lies outside the two extreme locations
(the case where $a > x_k$ is identical). %Let $\ell \geq 4$ be the number of distinct locations occupied by the agents in $\vec{x}$.
Without loss of generality, we assume that the selected instance $\vec{x}$ has the minimum number of distinct locations among all instances for which $F$ places a facility outside the two extremes. %Namely, we assume that for all instances $\vec{x}' \in \I(N)$ with at most $\ell-1$ distinct locations, $\min\vec{x}' \leq F_1(\vec{x}') \leq F_2(\vec{x}') \leq \max\vec{x}'$, and by what we have shown above, $F(\vec{x}') = (\min\vec{x}', \max\vec{x}')$.
%
Since $a < x_j$, either $x_j$ or $x_k$ is not allocated a facility by $F(\vec{x})$. Next, we assume that $x_j \not\in F(\vec{x})$ (the case where $x_k \not\in F(\vec{x})$ is symmetric). Let $S_j \subseteq N$ be the set of agents located at $x_j$, and let $b = \min\vec{x}_{-S_j}$ be the second location from the left in $\vec{x}$.
%We note that $S_j \neq \emptyset$, since $j \in S_j$.
Since $x_j \not\in F(\vec{x})$, there is a $x_j$-hole $(l, r)$ in the image set $I_{S_j}(\vec{x}_{-S_j})$.
%
We observe that $r \leq b$, because if all agents in $S_j$ move from $x_j$ to $b$, we obtain the instance $\vec{x}' = (\vec{x}_{-S_j}, b, \ldots, b)$ that has less distinct locations than $\vec{x}$ and $b$ as its leftmost location. Since $\vec{x}$ has the minimum number of distinct locations among all instances for which $F$ places a facility outside the two extremes, $F(\vec{x}')$ places a facility to $b$. %and thus $b \in I_{S_j}(\vec{x}_{-S_j})$.
%
We now choose $\eps > 0$ such that $r-\eps$ lies in the right half of the hole $(l, r)$, and move all agents in $S_j$ from $x_j$ to $r-\eps$. Thus, we obtain the instance $\vec{x}'' = (\vec{x}_{-S_j}, (r-\eps, \ldots, r-\eps))$. Since $F$ is strategyproof and $r$ is the closest location to $r-\eps$ in $I_{S_j}(\vec{x}_{-S_j})$, $F(\vec{x}'')$ places a facility at $r > r-\eps$ (see also \cite[Lemma~3.1]{LSWZ10}).
%
Therefore, $F(\vec{x}'')$ places a facility inside the two extremes of $\vec{x}''$, which contradicts what we have shown above: namely that if $F$ does not admit a dictator for 3-location instances, then $F$ never places a facility inside the two extremes. \qed





%The case where $F$ does not admit a dictator for 3-location instances is similar. The details can be found in the Appendix, Section~\ref{app:s:2fac-gen}. \qed


